Leetcode #207. Course Schedule

題目給你一系列的課程，每一個門課都有它的先修課，你要判斷它能不能完成全部的課程。
來舉個例子:
Input: numCourses = 2, prerequisites = [[0,1],[0,4],[1,2],[2,0]]
prerequisites裡面放的兩維array是Edge List儲存圖的方式，現在把它畫成圖。

完成0的課，需要先完成1、4，4的課沒有其他先修課，4是可以被完成的。1的先修是2，2的先修是0，結果又回到0，會造成無限的loop。
這時候我們就回傳false，表示不可能完成全部的課程。

換句話來說，我們檢查圖有沒有cycle就可以了!

這題會用DFS來解(你用BFS也可以)
用一個map來記下走過的課程，當0->1->2的時候，2又回到0就可以發現有cycle。
每一個課程都做一次DFS，基本上就解出來了，不過這做法的時間複雜度很高，會到O(n^2)，會有大量的重複走訪，在這一題leetcode會跑到timeout (慘痛經驗 XD
需要在這基礎上做優化，來換個例子解釋～

像這種情境，從課程0 DFS出去，0->1->2都沒有發現cycle。
這時候0、1、2，這幾個點都已經被檢查完成了，我們記錄下來，之後換到4做DFS，就不用再跑去1->2做重複的檢查，時間複雜度會降到O(m+n)，每一個課程+邊線都走一次，不會重複。

所以現在有兩個map要記

1. 記錄當下DFS的路線，用於檢查有沒有cycle
2. 記錄DFS完的課程，用於避免重複的檢查

把它寫成程式～

func canFinish(numCourses int, prerequisites [][]int) bool {
	// 先把Edge list格式轉成Adjacency list
    // ex: 0:[1,4] 1:[2]
	adjList := map[int][]int{}
	for _, pre := range prerequisites {
		adjList[pre[0]] = append(adjList[pre[0]], pre[1])
	}

	traced := map[int]bool{}
	checked := map[int]bool{}
	// 每個點都要做一次DFS哦
	for i := 0; i < numCourses; i++ {
		if hasCycle(i, adjList, traced, checked) {
			return false
		}
	}

	return true
}

func hasCycle(course int, adjList map[int][]int, traced, checked map[int]bool) bool {
	// 如果之前走過，證明是有cycle
	if traced[course] {
		return true
	}

	// 檢查之前有沒有檢查過，如果有就不重複
	if checked[course] {
		return false
	}

	traced[course] = true
	for _, pre := range adjList[course] {
		if hasCycle(pre, adjList, traced, checked) {
			return true
		}
	}
	// *這個map是用來記每個點DFS的記錄 走完要改回false
	traced[course] = false

	// DFS完 代表檢查完成 沒有cycle
	checked[course] = true

	return false
}

感謝大家～